#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    int maxDistance(vector<int> &colors)
    {
        int n = colors.size();
        int res = 0; // 两栋颜色不同房子的最远距离
        // 遍历两栋房子下标并维护最远距离
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (colors[i] != colors[j])
                {
                    res = max(res, j - i);
                }
            }
        }
        return res;
    }

    int maxDistance_2(vector<int> &colors)
    {
        int length = colors.size();
        // 如果首位颜色不同直接返回
        if (colors[0] != colors[length - 1])
        {
            return length - 1;
        }
        // 获取左边第一个不相同的位置
        int left = 1;
        while (colors[left] == colors[0])
        {
            left += 1;
        }
        // 获取右边第一个不相同的位置
        int right = length - 2;
        while (colors[right] == colors[length - 1])
        {
            right -= 1;
        }
        // 0～right 的长度 和 left～length-1 的长度取最大值
        // 因为要最大，所以不可能在中间，要么就是左边，要么就是右边
        return max(right, length - 1 - left);
    }
};
int main()
{
    Solution s;
    vector<int> colors = {1, 8, 3, 8, 3};
    cout << s.maxDistance_2(colors) << endl;
    return 0;
}